package lc.q150_200;

public class Q200 {

    class UnionFind {

        int[] parent;
        int[] rank;
        int count = 0;

        UnionFind(char[][] grid) {
            parent = new int[grid.length * grid[0].length];
            rank = new int[grid.length * grid[0].length];
            int n = grid.length;
            int m = grid[0].length;
            for (int i = 0; i < n; i++) {
                for (int i1 = 0; i1 < m; i1++) {
                    if (grid[i][i1] == '1') {
                        parent [i * m + i1] = i * m + i1;
                        ++ count;
                    }
                    rank[i * m + i1] = 0;
                }
            }
        }

        int find(int node) {
            if (parent[node] != node) {
                parent[node] = find(parent[node]);
            }
            return parent[node];
        }

        void union(int x, int y) {
            int rootx = find(x);
            int rooty = find(y);
            if (rootx != rooty) {
                if (rank[rootx] > rank[rooty]) {
                    // y合并到x
                    parent[rooty] = rootx;
                } else if (rank[rootx] < rank[rooty]) {
                    parent[rootx] = rooty;
                } else {
                    parent[rooty] = rootx;
                    rank[rootx] ++;
                }
                --count;
            }
        }

        int getCount() {
            return count;
        }

    }

    public int numIslandsByUF(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int n = grid.length;
        int m = grid[0].length;
        UnionFind unionFind = new UnionFind(grid);
        for (int i = 0; i < n; i++) {
            for (int i1 = 0; i1 < m; i1++) {
                if (grid[i][i1] == '1') {
                    // 查看邻居是否为1，是的话结合一起
                    if (i  > 0 && grid[i - 1][i1] == '1') {
                        unionFind.union(i * m + i1, (i - 1) * m + i1);
                    }
                    if (i + 1 < n && grid[i + 1][i1] == '1') {
                        unionFind.union(i * m + i1, (i + 1) * m + i1);
                    }
                    if (i1 -1 >= 0 && grid[i][i1 - 1] == '1') {
                        unionFind.union(i * m + i1, i * m + i1 - 1);
                    }
                    if (i1 +1 < m && grid[i][i1 + 1] == '1') {
                        unionFind.union(i * m + i1, i * m + i1 + 1);
                    }
                }
            }
        }
        return unionFind.getCount();
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int n = grid.length;
        int m = grid[0].length;
        int nums = 0;
        for (int i = 0; i < n; i++) {
            for (int i1 = 0; i1 < m; i1++) {
                if (grid[i][i1] == '1') {
                    nums ++;
                    dfs(grid, i, i1);
                }
            }
        }
        return nums;
    }

    private void dfs(char[][] grid, int x, int y) {
        int nr = grid.length;
        int nc = grid[0].length;
        if (x < 0 || y < 0 || x >= nr || y >=nc || grid[x][y] == '0') {
            return;
        }
        grid[x][y] = '0';
        dfs(grid,x - 1, y);
        dfs(grid, x + 1, y);
        dfs(grid,x, y - 1);
        dfs(grid,x, y + 1);
    }

}
